package DP;

/**
 * https://leetcode-cn.com/problems/house-robber/
 * 这个和求总和，数字不能相邻一样，灯叔的题
 *
 */
public class HouseRobber {

    /**
     * 转移方程就是，偷x的最大是多少
     * F[x] = max(偷F[x] + F[x-2], 不偷F[x] + F[x-1])
     */
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 0){
            return 0;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = nums[0];

        for(int i=2; i <= n; i++){
            dp[i] = Math.max(dp[i-2] + nums[i-1], dp[i-1]);
        }

        return dp[n];
    }
    //滚动数组
    public int rob2(int[] nums) {
        int n = nums.length;
        if(n == 0){
            return 0;
        }
        if(n==1){
            return nums[0];
        }
        //这里要特别注意，谁是old，谁是now
        int old=0;
        int now=nums[0];
        int tmp;

        for(int i=2; i <= n; i++){
            //要做一下临时值存储，以及新的值赋值
            tmp = now;
            now = Math.max(old + nums[i-1], now);
            old = tmp;
        }

        return now;
    }

    /**
     * 房子围成 https://leetcode-cn.com/problems/house-robber-ii/
     * 围城一圈，就是多加一个条件，偷最后一个，就不能偷第一个。
     */
    public int robII(int[] nums) {
        return 0;
    }


    public static void main(String[] args){
        int[] n = new int[]{-1,1,1,1};

    }


}
